//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
// 
//
// 示例 2: 
//
// 
//输入: nums = [1], k = 1
//输出: [1] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// k 的取值范围是 [1, 数组中不相同的元素的个数] 
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 
// 
//
// 
//
// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 
// Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 
// 👍 912 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentElements {
    public static void main(String[] args) {
        Solution solution = new TopKFrequentElements().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 找出按照出现次数由高到低排序的前k个
         * 直接想到的就是进行hash统计，但是统计完之后再统计前三个高的又是一件麻烦事
         * 空间复杂度我觉得太高了，使用了一个HashMap不说，还创建了一个temp数组储存并排序
         * 时间复杂度为nlogn，空间复杂度为N
         */
        public int[] myTopKFrequent(int[] nums, int k) {
            int[] res = new int[k];
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums){
                //计数
                map.put(num, map.getOrDefault(num, 0)+1);
            }
            int[] temp = new int[map.size()];
            int i = 0;
            for (int count : map.values()){
                //取出所有出现的次数
                temp[i] = count;
                i++;
            }
            Arrays.sort(temp);//将次数进行排序
            i = 0;
            for (Map.Entry<Integer,Integer> entry : map.entrySet()){
                //TODO 将次数>=倒数第K个的元素加入结果集中去，这个地方挺巧的
                if (entry.getValue()>= temp[map.size()-k]){
                    res[i++] = entry.getKey();
                }
            }
            return res;
        }

        /**
         * 使用小顶堆来实现元素出现次数的筛选
         * 小顶堆的比较器要重写一下才行，是按照map的value的大小来排序的
         * 题解：
         * 1.使用hashmap统计元素出现次数之后创建并维护一个小顶堆来进行最终元素的筛选
         * 2.仍然是使用一个额外的hashmap进行次数的统计，统计完之后利用桶排序的思想
         *  将出现次数作为下标进行元素的存储，使用List来保存，长度是原数组长度+1（牺牲一些空间防止越界）
         *  但是这样遍历的话结果集也是list才能添加，遍历时如果list[i]为空时就不添加了
         */
        public int[] topKFrequent(int[] nums, int k) {
            int[] res = new int[k];
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums)//计数
                map.put(num, map.getOrDefault(num, 0)+1);

            //重写比较器，实现对map中value的比较
            PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)-> map.get(a)-map.get(b));
            for (int key : map.keySet()){
                if(pq.size() < k){
                    pq.add(key);
                }else if(map.get(key) > map.get(pq.peek())){
                    pq.poll();
                    pq.add(key);
                }
            }
            for (int i = k-1; i >=0; i--) {
                res[i] = pq.poll();
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}



















